206 反转链表

https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnnhm6/

https://leetcode.cn/problems/reverse-linked-list/description/

cost: 递归 16m6s，循环 8m29s

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

// 递归
class Solution {
public:
    ListNode* reverseList(ListNode* node) {
        if (node == nullptr || node->next == nullptr) {
            return node;
        }
        ListNode* head = this->reverseList(node->next);
        node->next->next = node;
        node->next = nullptr;
        return head;
    }
};

// 循环
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr) {
            return nullptr;
        }
        auto p = head;
        auto pNext = head->next;
        head->next = nullptr;
        while (p != nullptr && pNext != nullptr) {
            auto tmp = pNext->next;
            pNext->next = p;
            p = pNext;
            pNext = tmp;
        }
        return p;
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(1)